package com.yulan.hash;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 49. 字母异位词分组
 * 质数Hash法
 */
public class LeetCode_49 {
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
            73, 79, 83, 89, 97, 101};

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Integer,List<String>> map = new HashMap<>();

        for(String str:strs){
            int rootHash = 1;

            for(char c : str.toCharArray()){
                rootHash *= primes[c-'a'];
            }

            if(map.containsKey(rootHash)){
                map.get(rootHash).add(str);
            }else{
                map.put(rootHash,new ArrayList<String>(){{add(str);}});
            }
        }
        return new ArrayList<>(map.values());
    }


    @Test
    public void test(){
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        for(List<String> list : groupAnagrams(strs)){
            System.out.println(list);
        }
    }


}
